This invention relates to machine vision, and particularly to determining a reference point, such as the center, of an object profile of unknown size but known shape using a machine vision system.
It is known in the machine vision industry how to search for an object of a known size and shape in an image. Such techniques are used to align a template of the object with the image of the object so that further processes can inspect portions of the object, such as printing on the surface of the object, roundness of the object, or the presence/absence of a pill contained in the object.
Here, an image is a rectangular, two-dimensional array of grey values, where each element in the array is called a pixel. A template is similar to an image, except that it need not be rectangular, or even simply connected, i.e. it may consist of a collection of disjoint regions. A template is similar to an image also in that each element of the template is assigned a grey value.
In general, the methodology for searching for an object of known size and shape in an image is to first construct the template of the object; then search a likely area of the image of the object for the portion of the image to which the template is most similar. Various methods, such as that taught in U.S. Pat. No. 5,548,326
Efficient Image Registration, have been developed to improve the efficiency of such searches.
Once the object is found, it can be said to be aligned with respect to the template. Alignment shall be defined as orienting the object with respect to the template to make at least one alignment parameter of the object, such as the planar position, substantially equal to the corresponding alignment parameter of the template. After alignment, commonly, the machine vision system returns a metric representative of the goodness of fit, a measure of the aggregate deviations of the actual object from the template.
However, when the size of the object to be found is unknown, the known search techniques have had to be modified to include multiple templates of various sizes. Multiple templates are needed because typically such techniques search for objects that are the same size as the template. The techniques typically compare pixels of the image to elements of the template for a match. Thus, the pixel values of the image and the elements of the template will not correspond unless an appropriately scaled template with appropriate number and arrangement of elements is used. However, it is not always possible to know which sizes of the template are required for effective searching.
The possibility of flaws in the object further diminishes the usefulness of current search techniques for objects of an unknown size. Under such circumstances, known techniques take an unacceptably long time. Further, even when given a longer time to search, known techniques have difficulty distinguishing between a perfect but differently sized object, and a flawed but correctly sized object.
An efficient and accurate alignment method and apparatus provides the position of a reference point, such as the center, of an xe2x80x9cobject profilexe2x80x9d, even when an exact size of the object, and thus the size of the profile of the object, is unknown. The method generates a synthetic labeled-projection model based upon the xe2x80x9cobject profilexe2x80x9d to be found, acquires an image of the object, and defines a window to enclose at least a portion of the image. The image is evaluated by performing a normalized labeled projection of the image of the object using the model of the object at each location in the image within the window, which generates a histogram of the image for each location. The histogram is a representation of all pixels in the image that are similarly labeled in the labeled-projection model. Next, the histogram is differentiated and the maximum absolute value is noted for each location. Thereafter, a comparison can be made between the maximum absolute values of the first derivative of each of the locations. Ultimately, the peak of the maximum absolute values of the first derivative is determined. The position of the labeled-projection model associated with the peak provides the position of the reference point of the xe2x80x9cobject profile.xe2x80x9d More particularly, the position of the center of the labeled-projection model associated with the peak is the position of the center of the xe2x80x9cobject profile.xe2x80x9d
The first derivative of the histogram is greatest when a feature of the image, such as the xe2x80x9cobject profilexe2x80x9d, is aligned with a feature denoted by a specific label of the labeled-projection model, such as the shape of the xe2x80x9cobject profile.xe2x80x9d Therefore, the method uses the peak of the all the histogram""s first derivatives to find the reference point of the xe2x80x9cobject profilexe2x80x9d. Since flaws in the object will rarely align with labels of the labeled-projection model, the flaws will not significantly effect finding the reference point of the xe2x80x9cobject profilexe2x80x9d. Moreover, the labeled-projection model is labeled such that xe2x80x9cobject profilesxe2x80x9d of varying sizes can be found.
Not only can the xe2x80x9cobject profilexe2x80x9d be found despite flaws and unknown size, but the reference point of the xe2x80x9cobject profilexe2x80x9d can also be found efficiently. In one embodiment, more than one window is defined to reduce the area of the image at which the normalized labeled projection must be performed for each position of the labeled-projection model, thereby, enhancing efficiency. The multiple windows of this embodiment enclose a smaller area of the image than the single window of the previous embodiment. Although a smaller area is searched for each normalized labeled projection, the xe2x80x9cobject profilexe2x80x9d is identified because the smaller windows are defined to enclose enough of the xe2x80x9cobject profilexe2x80x9d within the windows. Thus, use of more than one small window enhances the efficiency of the method and apparatus by decreasing the number of computations required without substantially decreasing reliability.
In a preferred embodiment, the number of times the labeled-projection model is moved with respect to die image is decreased to enhance efficiency. Two or more one-dimensional searches are used to increment the labeled-projection model""s position as opposed to an area search of an alternative embodiment.
In particular, when there is greater uncertainty about the size of objects to be inspected, the invention obtains more accurate and faster results than known methods, which is advantageous in many inspection applications.